package main.java.sort;

import main.java.ArrayUtils;

public class InsertionSort {

	public static void main(String[] args) {
		Integer[] array = new Integer[]{5, 2, 4, 6, 8, 1, 3, 7};
		for (int j = 1; j <= array.length - 1; j++) { //从第二个数字开始
			int key = array[j]; //记录下当前要插入的数据

			int i = j - 1; //插入到0到j-1的原有数组中
			while (i >= 0 && key < array[i]) {
				array[i + 1] = array[i];    //当前i往后移
				i--;
			}
			array[i + 1] = key;
		}
		//遍历输出数组
		int i = 0;
		while (i <= array.length - 1) {
			System.out.print(array[i++] + " ");
		}

	}


}
